package lib;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang.StringUtils;

import com.google.common.collect.ImmutableSet;

public class MathLib {

	private static final Primes PRIMES = new Primes();

	/**
	 * Dijkstra's solution
	 * @param n
	 * @return
	 * @see http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#exact
	 */
	public static BigInteger fibo(int n) {
		if (n == 0) return BigInteger.ZERO;
		if (n == 1) return BigInteger.ONE;
		if (n % 2 == 0) {
			BigInteger fiboN = fibo(n/2);
			BigInteger fiboNMin1 = fibo((n/2)-1);
			return fiboN.multiply(fiboN.add(fiboNMin1).add(fiboNMin1));
		} else {
			BigInteger fiboN = fibo((n+1)/2);
			BigInteger fiboNMin1 = fibo(((n+1)/2)-1);

			return fiboN.pow(2).add(fiboNMin1.pow(2));
		}
	}

	public static boolean isLychrel(int number, int iterations) {
		BigInteger intermediate = BigInteger.valueOf(number);
		for (int i = 1; i <= iterations; i++) {
			BigInteger reverse = new BigInteger(StringUtils.reverse(intermediate.toString()));
			intermediate = intermediate.add(reverse);
			if (isPalindromeInBase10(intermediate)) return false;
		}

		return true;
	}

	public static boolean isPalindrome(Number p, int base) {
		String s = toBigInteger(p).toString(base);

		for (int i = 0; i < (s.length() / 2) + 1; i++) {
			if (s.charAt(i) != s.charAt(s.length() - (i + 1))) return false;
		}

		return true;

	}

	public static boolean isPalindromeInBase2(Number p) {
		return isPalindrome(p, 2);
	}

	public static boolean isPalindromeInBase10(Number p) {
		return isPalindrome(p, 10);
	}

	public static boolean isEvenlyDivisible(long dividend, long divisor) {
		return dividend % divisor == 0;
	}

	/**
	 * Decompose a number into its prime factors. Factors can occur multiple times; e.g. for an input
	 * of "8", the result will be a List containing three elements, each a Long of the value "2".
	 * @param n The number to decompose; must be a non-negative integer.
	 * @return a list of factors. If the input is prime, the result will contain only that number. 
	 */
	public static List<Integer> factorize(long n) {
		if (n < 0) throw new IllegalArgumentException();
		List<Integer> factors = new ArrayList<Integer>();
		if (n < 2) {
			factors.add((int)n);
			return factors;
		}
		
		for (long primeIndex = 1, prime = PRIMES.getPrime((int)primeIndex); prime <= n; prime = PRIMES.getPrime((int)++primeIndex)) {
			while (isEvenlyDivisible(n, prime)) {
				n /= prime;
				factors.add((int)prime);
			}
		}

		return factors;
	}

	public static Set<Integer> distinctFactors(int n) {
		return ImmutableSet.copyOf(factorize(n));
	}
	
	public static int numberOfDistinctFactors(int n) {
		return distinctFactors(n).size();
	}

	public static long getPrime(int n) {
		return PRIMES.getPrime(n);
	}
	
	public static boolean isPrime(int i) {
		return PRIMES.isPrime(i);
	}
	
	public static long getProduct(Collection<? extends Number> list) {
		if (list == null || list.size() == 0) return 0L;
		long result = 1;
		for (Number n: list) {
			result *= n.longValue();
		}
		return result;
	}

	public static long getSum(Collection<? extends Number> list) {
		if (list == null || list.size() == 0) return 0L;
		long result = 0L;
		for (Number n: list) {
			result += n.longValue();
		}
		return result;
	}
	
	public static long getSum(Number... list) {
		long result = 0L;
		for (Number n : list) {
			result += n.longValue();
		}
		return result;
	}

	public static long getGreatest(Collection<? extends Number> list) {
		long greatest = Long.MIN_VALUE;
		for (Number n: list) {
			if (n.longValue() > greatest) greatest = n.longValue();
		}
		return greatest;
	}

	public static long getSmallest(Collection<? extends Number> list) {
		long smallest = Long.MAX_VALUE;
		for (Number n: list) {
			if (n.longValue() < smallest) smallest = n.longValue();
		}
		return smallest;
	}

	public static List<Long> getDivisors(long l) {
		List<Long> divisors = getProperDivisors(l);

		divisors.add(l);

		return divisors;
	}

	public static List<Long> getProperDivisors(long number) {
		List<Long> divisors = new ArrayList<Long>();

		for (long divisor = 1; divisor <= number/2; divisor++) {
			if (isEvenlyDivisible(number, divisor)) divisors.add(divisor);
		}
		return divisors;
	}

	/**
	 * 
	 * @param n
	 * @return
	 * @see http://en.wikipedia.org/wiki/Divisor_function#Properties
	 */
	public static int getNumDivisors(long n) {
		List<Integer> factors = factorize(n);
		Map<Integer, Integer> powers = new HashMap<Integer, Integer>();
		for (int factor : factors) {
			powers.put(factor, Collections.frequency(factors, factor));
		}

		int numDivisors = 1;
		for (int power : powers.keySet()) {
			numDivisors *= powers.get(power) + 1;
		}
		return numDivisors;
	}

	public static BigInteger getPolygonalNumber(Number n, long sides) {
		BigInteger nBI = toBigInteger(n);
		//in words: ((sides - 2) n^2 - (sides - 4) n) / 2 (see http://en.wikipedia.org/wiki/Polygonal_number#Formulae)
		return nBI.pow(2).multiply(BigInteger.valueOf(sides - 2)).subtract(nBI.multiply(BigInteger.valueOf(sides - 4))).divide(BigInteger.valueOf(2)); 
	}


	/**
	 * The formula from wikipedia says:
	 * (sqrt((8s - 16)x + (s-4)^2) + s - 4) / (2s - 4) must be an integer number. If that is true, then the enumerator mod divisor must be zero. 
	 * @param n
	 * @param sides
	 * @return
	 */
	public static boolean isPolygonalNumber(Number x, long sides) {
		BigInteger xB = toBigInteger(x);
		if (xB.compareTo(BigInteger.ZERO) != 1) return false;
		BigInteger sqrtPart = 
			xB.multiply(BigInteger.valueOf(8*sides - 16))
			.add(BigInteger.valueOf(sides - 4).pow(2));
		if (!isPerfectSquare(sqrtPart)) return false;
		BigInteger computedSqrt = integerSquareRoot(sqrtPart);
		BigInteger enumerator = computedSqrt.add(BigInteger.valueOf(sides - 4));
		BigInteger divisor = BigInteger.valueOf((2*sides) - 4);
		return enumerator.mod(divisor).compareTo(BigInteger.ZERO) == 0;
	}

	public static Long pascal(long row, long column) {
		if (column == 0) return 1L;
		Long previousColumn = pascal(row, column - 1);
		Double factorThisCell = ((double)row - column) / column;
		return Math.round(previousColumn * factorThisCell);
	}
	
	//XXX: wicked slow for small n!
	public static BigInteger factorial(Number n) {
		BigInteger answer = BigInteger.ONE;
		for (BigInteger i = BigInteger.valueOf(2), end = toBigInteger(n); i.compareTo(end) < 1; i = i.add(BigInteger.ONE)) {
			answer = answer.multiply(i);
		}
		return answer;
	}

	public static BigInteger multiplicativeOrder(BigInteger number, BigInteger modulo) {
		for (BigInteger i = BigInteger.ONE; i.compareTo(BigInteger.valueOf(999999999)) < 0; i = i.add(BigInteger.ONE)) {
			if (BigInteger.ONE.equals(number.modPow(i, modulo))) return i;
		}
		return null; //yeah, right.
	}

	public static BigInteger choose(Number amount, Number from) {
		BigInteger n = toBigInteger(from);
		BigInteger r = toBigInteger(amount);
		BigInteger nMinR = n.subtract(r);

		if (r.compareTo(nMinR) > 0) { //swap them so r is the greater one
			nMinR = r;
			r = n.subtract(r);
		}

		BigInteger result = BigInteger.ONE;

		for (BigInteger i = n; i.compareTo(r) > 0; i = i.subtract(BigInteger.ONE)) {
			result = result.multiply(i);
		}

		return result.divide(factorial(nMinR));
	}

	private static BigInteger toBigInteger(Number n) {
		if (n instanceof BigInteger) {
			return (BigInteger) n;
		} else if (n instanceof BigDecimal) {
			return ((BigDecimal) n).toBigIntegerExact();
		} else {
			return BigInteger.valueOf(n.longValue());
		}
	}

	/**
	 * Simplified from http://stackoverflow.com/questions/295579/
	 * @param n
	 * @return
	 */
	public static boolean isPerfectSquare(Number n) {
		BigInteger nBI = toBigInteger(n);

		//negatives are not perfect squares, zero is
		if (nBI.signum() == -1) {
			return false;
		} else if (nBI.signum() == 0){
			return true;
		}


		//Squares in base 16 must end in 0, 1, 4, or 9, so if this number does not, bail early.
		if (nBI.testBit(1)) return false;
		if (nBI.and(BigInteger.valueOf(7)).shortValue() == 5) return false;
		if (nBI.and(BigInteger.valueOf(11)).shortValue() == 8) return false;

		//TODO: use BAD255 for speedup
		//Check mod 255 = 3 * 5 * 17, for fun
		//		long y = n;
		//		y = (y & 0xffffffffL) + (y >> 32);
		//		y = (y & 0xffffL) + (y >> 16);
		//		y = (y & 0xffL) + ((y >> 8) & 0xffL) + (y >> 16);
		//		if( BAD255[(int)y] )
		//			return false;


		int greatestPowerOfTwo = nextPowerOfTwo(nBI);

		BigInteger nWithoutPowersOfFour = nBI;
		for (int powerOfTwo = greatestPowerOfTwo; powerOfTwo >= 2; powerOfTwo /= 2) {
			BigInteger twoRaisedToPowerMinusOne = BigInteger.valueOf(2).pow(powerOfTwo).subtract(BigInteger.ONE);
			if ((nWithoutPowersOfFour.and(twoRaisedToPowerMinusOne)).equals(BigInteger.ZERO)) {
				nWithoutPowersOfFour = nWithoutPowersOfFour.shiftRight(powerOfTwo);
			}
		}

		if (!nWithoutPowersOfFour.and(BigInteger.valueOf(7)).equals(BigInteger.ONE)) {
			return false;
		}

		BigInteger r, t, z;
		r = BigInteger.ONE; //TODO: use a lookup table for starting numbers for better performance
		do {
			z = nWithoutPowersOfFour.subtract(r.multiply(r));
			if (z.signum() == 0) return true;
			if (z.signum() == -1) return false;
			t = z.and(z.negate());
			r = r.add(z.and(t).shiftRight(1));
			if (r.compareTo(t.shiftRight(1)) == 1) {
				r = t.subtract(r);
			}
		} while (t.bitLength() <= greatestPowerOfTwo);

		return false;
	}

	/**
	 * Adapted from Wikipedia: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
	 * @param number
	 * @return
	 */
	public static BigInteger integerSquareRoot(Number number) {
		BigInteger op = toBigInteger(number), res = BigInteger.ZERO, one = BigInteger.ONE.shiftLeft(nextPowerOfTwo(op) - 2);
		if (op.signum() == -1) throw new IllegalArgumentException("parameter must be positive");
		while (one.compareTo(op) == 1) {
			one = one.shiftRight(2);
		}
		while (one.signum() != 0) {
			BigInteger resPlusOne = res.add(one);
			if (op.compareTo(resPlusOne) >= 0) {
				op = op.subtract(resPlusOne);
				res = res.shiftRight(1).add(one);
			} else {
				res = res.shiftRight(1);
			}
			one = one.shiftRight(2);
		}

		return res;
	}

	private static int nextPowerOfTwo(BigInteger n) {
		int nextPowerOfTwo = n.bitLength();
		nextPowerOfTwo--;
		nextPowerOfTwo |= nextPowerOfTwo >> 1;  // handle  2 bit numbers
		nextPowerOfTwo |= nextPowerOfTwo >> 2;  // handle  4 bit numbers
		nextPowerOfTwo |= nextPowerOfTwo >> 4;  // handle  8 bit numbers
		nextPowerOfTwo |= nextPowerOfTwo >> 8;  // handle 16 bit numbers
		nextPowerOfTwo |= nextPowerOfTwo >> 16; // handle 32 bit numbers
		nextPowerOfTwo++;
		return nextPowerOfTwo;
	}
	
	public static BigInteger sumOfDigitsRaisedToPower(Number number, int power) {
		BigInteger n = toBigInteger(number);
		BigInteger sumOfPowers = BigInteger.ZERO;
		for (String digit : n.toString().split("")) {
			if (!"".equals(digit)) {
				sumOfPowers = sumOfPowers.add(new BigInteger(digit).pow(power));
			}
		}
		return sumOfPowers;
	}

	
	public static int sumOfDigitsRaisedToPower(int number, int power) {
		int sumOfPowers = 0;
		while (number > 0) {
			int lowestDigit = number%10;
			int digitRaisedToPower = lowestDigit;
			for (int i = 1; i < power; i++) {
				digitRaisedToPower *= lowestDigit;
			}
			sumOfPowers += digitRaisedToPower;
			number /= 10;
		}
		return sumOfPowers;
	}
	
	public static Number phi(int n) {
		Fraction answer = new Fraction(n);  
		for (Integer factor : distinctFactors(n)) {
			answer = answer.times(new Fraction(factor - 1, factor));
		}
		return answer.normalized().numerator;
	}
	
	public static Number sumOfTotient(int n) {
		BigInteger answer = BigInteger.ONE;
		for (int i = 1; i <= n; i++) {
			answer = answer.add(toBigInteger(phi(i)));
		}
		return answer;
	}

}
